import java.util.Arrays;

public class sort {
    public static void main(String[] args) {
        int[] n = {9, 8, 7, 6, 5, 4, 3, 2, 1};
        maopao(n);
        charu(n);
        quickSort(n, 0, n.length - 1);
        for (int e : n) {
            System.out.print(e + " ");
        }
        System.out.println();
        merge_Sort(n);
        for (int e : n) {
            System.out.print(e + " ");
        }
    }

    //冒泡排序
    public static void maopao(int[] n) {
        int i, j, l = n.length, temp;
        for (i = 0; i < l; i++) {
            for (j = 1; j < l - i; j++) {
                if (n[j] < n[j - 1]) {
                    temp = n[j];
                    n[j] = n[j - 1];
                    n[j - 1] = temp;
                }
            }
        }
        for (int e : n) {
            System.out.print(e + " ");
        }
        System.out.println();
    }

    //插入排序
    public static void charu(int[] n) {
        int i, j, l = n.length, temp;
        for (i = 1; i < n.length; i++) {
            for (j = i - 1; j >= 0; j--) {
                if (n[i] < n[j]) {
                    temp = n[i];
                    n[i] = n[j];
                    n[j] = temp;
                }
            }
        }
        for (int e : n) {
            System.out.print(e + " ");
        }
        System.out.println();

    }

    public static void quickSort(int[] n, int _left, int _right) {
        int left = _left;
        int right = _right;
        int temp = 0;
        if (left <= right) {   //待排序的元素至少有两个的情况
            temp = n[left];  //待排序的第一个元素作为基准元素
            while (left != right) {   //从左右两边交替扫描，直到left = right

                while (right > left && n[right] >= temp)
                    right--;        //从右往左扫描，找到第一个比基准元素小的元素
                n[left] = n[right];  //找到这种元素arr[right]后与arr[left]交换

                while (left < right && n[left] <= temp)
                    left++;         //从左往右扫描，找到第一个比基准元素大的元素
                n[right] = n[left];  //找到这种元素arr[left]后，与arr[right]交换

            }
            n[right] = temp;    //基准元素归位
            quickSort(n, _left, left - 1);  //对基准元素左边的元素进行递归排序
            quickSort(n, right + 1, _right);  //对基准元素右边的进行递归排序
        }
    }
    public static void merge_Sort(int[] arr){
        int length = arr.length;
        int mid = length/2;
        if(length > 1){
            int[] left = Arrays.copyOfRange(arr, 0, mid);//复制左半部分
            int[] right = Arrays.copyOfRange(arr, mid, length);//复制右半部分
            merge_Sort(left);//递归左边
            merge_Sort(right);//递归右边
            merge(arr,left,right);//合并数组
        }
    }
    public static void merge(int[] result, int[] left, int[] right){
        int i = 0, l = 0, r = 0;
        while(l < left.length && r < right.length){
            if(left[l] < right[r] )
                result[i++] = left[l++];
            else
                result[i++] = right[r++];
        }
        while(l < left.length){//若left数组剩余，则后面依次复制给result
            result[i++] = left[l++];
        }
        while(r < right.length){//反之
            result[i++] = right[r++];
        }
    }
}
